O(n)
O(log n)
h
k
L
f
X f(X)
T f X
Y
m
f ←
˜
X = X
k = 1 . . . , m
f
(k)
= L(
˜
mX)
f ← f
(k)
◦ f
˜
mX ← f
(k)
(
˜
mX)
f ← T (f, X, Y )
f
400
1 4
y
x P (x)
P (y|x) P (x)
P (x) P (y | x)
y x y x
y x
P
1
P
2
P
1
P
2
P
1
P
2
selection switch
x
(1)
x
(2)
x
(3)
h
(3)
h
(2)
h
(1)
y
y x
x
(1)
x
(2)
x
(3)
P
1
P
2
P
1
P
2
task specification t
output f
t
(x)
t
f
t
(x) t
x y
X
Y
X
Y
(x, y)
(x, y) x y
x y
P (x) (x, y)
P (y | x)
X
x
1
x
2
P (x) P (x, y) P (y | x)
−log P (y | x)
−log P (x) −log P (x, y)
P (x) P (y | x)
P (x) P (y | x)
P (x)
x
y x
x y
P (y | x) x P (x)
P (x) P (y | x)
P (x) E[y | x]
x P (y | x)
x
y
P (x)
P (y | x) P (y | x) P(x)
y x
P (x) P (y | x)
y x h
0 5 10 15 20
x
0.0
0.1
0.2
0.3
0.4
0.5
p(x)
y=1 y=2 y=3
Mixture model
x
y
p(x) y
h x
P (h, x) = P (x | h)P (h).
P (x) =
P (x | h)p(h)dh
P (x) =
h
P (x | h)P (h).
x
h
x
y
y
y x
P (y | x) =
P (x | y)P (y)
P (x)
.
P (x) P (y | x)
h y = h
i
h
j
y h
x y P (x | y)
P (y)
P (x | y) P (y)
h P (x | h)
n
2
n
n
n
n
n
n
• k
• k
•
•
•
• n
w
1
w
2
C1 C2 C3
k n n
O(n
k
)
u ≈ v f
f(u) ≈ f(v)
(x, y) f(x) ≈ y
ˆ
f
n d
n
d
f 2
d
O(2
d
)
n R
d
d
j=0
n
j
= O(n
d
),
2
d
O(d)
O(n
d
)
n
k
k − 1
x
2
x
3
x
2
x
3
d
L n
O
n
d
d(L−1)
n
d
,
L k
O
k
(L−1)+d
.
y = h
i
x
• f x ≈ y
f(x) ≈ f(y)
•
•
• x
P (x)
P (y | x) P (y | x)
P (x)
P (x) P (y | x)
•
y
i
x
f
i
(x) x
y
i
h
P (y
i
| x) P (h | x)
•
•
P (x | = i) i
•
• x
x
•
P (h) =
i
P (h
i
)